算法-二分查找详解[多语言实现]

二分查找(Binary Search)是一种高效的查找算法,常用于有序数组或序列。根据循环条件和区间定义的不同,二分查找可以有多种写法,主要包括以下四种:


1. 闭区间 [left,right]

搜索区间是闭区间 [left, right]

代码模板:

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binary_serach(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1; // 定义闭区间 [left, right]
while (left <= right) { // 区间不为空时继续查找
int middle = left + (right - left) / 2;
if (nums[middle] == target) {
return middle;
}
else if (nums[middle] < target) {
left = middle + 1;
}
else {
right = middle - 1;
}
}
return -1;
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var binary_search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
while(left <= right){
let middle = Math.floor((left + right) / 2);
if(nums[middle] === target){
return middle;
}else if(nums[middle] < target){
left = middle + 1;
}else{
right = middle - 1;
}
}
return -1;
};

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func binary_search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := left + (right-left)/2
if nums[middle] == target {
return middle
} else if nums[middle] < target {
left = middle + 1
} else {
right = middle - 1
}
}
return -1
}

python:

1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums, target):
left, right = 0, len(nums) - 1 # 定义闭区间 [left, right]
while left <= right: # 区间不为空时继续查找
middle = left + (right - left) // 2 # 防止溢出的计算方式
if nums[middle] == target:
return middle # 找到目标值
elif nums[middle] < target:
left = middle + 1 # 目标值在右侧
else:
right = middle - 1 # 目标值在左侧
return -1 # 未找到目标值

特点:

  • 循环条件是 left <= right。// 为什么是小于等于,因为当left=right的时候,还有一个元素没有进行比较
  • 更新指针时需要调整 left = middle + 1right = middle - 1
  • 适用于大多数查找场景。
  • 目标值未找到:此时,leftright 会交错,left 可能会越过 right,即 left 会比 right 大。// 我的理解:指针交错

2. 左闭右开 [left,right)

搜索区间为左闭右开 [left, right)

代码模板:

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binary_serach(vector<int>& nums, int target) {
int left = 0;
int right = nums.size(); // 定义左闭右开区间 [left, right)
while (left < right) { // 区间不为空时继续查找
int middle = left + (right - left) / 2; // 向下取整
if (nums[middle] == target) {
return middle;
}
else if (nums[middle] < target) {
left = middle + 1;
}
else {
right = middle;
}
}
return -1;
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var binary_search = function(nums, target) {
let left = 0;
let right = nums.length;
while(left < right){
let middle = Math.floor((left + right) / 2);
if(nums[middle] === target){
return middle;
}else if(nums[middle] < target){
left = middle + 1;
}else{
right = middle;
}
}
return -1;
};

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func binary_search(nums []int, target int) int {
left, right := 0, len(nums)
for left < right {
middle := left + (right-left)/2
if nums[middle] == target {
return middle
} else if nums[middle] < target {
left = middle + 1
} else {
right = middle
}
}
return -1
}

python:

1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums, target):
left, right = 0, len(nums) # 定义左闭右开区间 [left, right)
while left < right: # 区间不为空时继续查找
middle = left + (right - left) // 2
if nums[middle] == target:
return middle # 找到目标值
elif nums[middle] < target:
left = middle + 1 # 目标值在右侧
else:
right = middle # 目标值在左侧
return -1 # 未找到目标值

特点:

  • 循环条件是 left < right
  • 更新指针时,left = middle + 1right = middle
  • 更适合实现一些需要明确界限的算法(如快速插入位置)。
  • 目标值未找到:此时,left 会指向目标值应该插入的位置(即大于目标值的位置),right 会指向比目标值小的位置。// 我的理解:两个指针一起指在左边

3. 左开右闭 (left,right]

搜索区间为左开右闭 (left, right]

代码模板:

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binary_serach(vector<int>& nums, int target) { // (left,right]
int left = -1;
int right = nums.size() - 1; // 定义左开右闭区间 (left, right]
while (left < right) { // 区间不为空时继续查找
int middle = left + (right - left + 1) / 2; // 向上取整
if(nums[middle] == target) {
return middle;
}
else if (nums[middle] < target) {
left = middle;
}
else {
right = middle - 1;
}
}
return -1;
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var binary_search = function(nums, target) {
let left = -1;
let right = nums.length-1;
while(left < right){
let middle = Math.ceil((left + right) / 2);
if(nums[middle] === target){
return middle;
}else if(nums[middle] < target){
left = middle;
}else{
right = middle - 1;
}
}
return -1;
};

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func binary_search(nums []int, target int) int {
left, right := -1, len(nums)-1
for left < right {
middle := left + (right-left+1)/2
if nums[middle] == target {
return middle
} else if nums[middle] < target {
left = middle
} else {
right = middle - 1
}
}
return -1
}

python:

1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums, target):
left, right = -1, len(nums) - 1 # 定义左开右闭区间 (left, right]
while left < right: # 区间不为空时继续查找
middle = left + (right - left + 1) // 2 # 注意向上取整
if nums[middle] == target:
return middle # 找到目标值
elif nums[middle] < target:
left = middle # 目标值在右侧
else:
right = middle - 1 # 目标值在左侧
return -1 # 未找到目标值

特点:

  • 循环条件是 left < right
  • 更新指针时,left = middleright = middle - 1
  • 通常需要调整初始值。
  • 目标值未找到:此时,left 会指向目标值应该插入的位置(即大于目标值的位置),right 会指向目标值应该插入的位置,或者是小于目标值的位置。// 我的理解:两个指针一起指在右边

4. 开区间 (left,right)

搜索区间为开区间 (left, right)

代码模板:

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binary_serach(vector<int>& nums, int target) { // (left,right)
int left = -1;
int right = nums.size(); // 定义开区间 (left, right)
while (left + 1 < right) { // 同时left+1
int middle = left + (right - left) / 2; // 向下取整
if (nums[middle] == target) {
return middle;
}
else if (nums[middle] < target) {
left = middle;
}
else {
right = middle;
}
}
return -1;
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var binary_search = function(nums, target) {
let left = -1;
let right = nums.length;
while(left+1 < right){
let middle = Math.floor((left + right) / 2);
if(nums[middle] === target){
return middle;
}else if(nums[middle] < target){
left = middle;
}else{
right = middle;
}
}
return -1;
};

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func binary_search(nums []int, target int) int {
left, right := -1, len(nums)
for left+1 < right {
middle := left + (right-left)/2
if nums[middle] == target {
return middle
} else if nums[middle] < target {
left = middle
} else {
right = middle
}
}
return -1
}

python:

1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums, target):
left, right = -1, len(nums) # 定义开区间 (left, right)
while left + 1 < right: # 区间至少有一个元素时继续查找
middle = left + (right - left) // 2
if nums[middle] == target:
return middle # 找到目标值
elif nums[middle] < target:
left = middle # 目标值在右侧
else:
right = middle # 目标值在左侧
return -1 # 未找到目标值

特点:

  • 循环条件是 left + 1 < right
  • 更新指针时,left = middleright = middle
  • 在某些特殊算法(如上下边界问题)中有用。
  • 目标值未找到:此时,leftright 都指向目标值应该插入的位置。// 我的理解:两个指针一左一右在两边,不交错

总结对比

区间类型初始值循环条件指针更新
闭区间[left,right]left = 0, right = n-1left <= rightleft = middle + 1right = middle - 1
左闭右开[left,right)left = 0, right = nleft < rightleft = middle + 1right = middle
左开右闭 (left,right]left = -1, right = n-1left < rightleft = middleright = middle - 1
开区间 (left,right)left = -1, right = nleft + 1 < rightleft = middleright = middle